#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>

typedef char DataType;

typedef struct {
  DataType* a;
  int top;
  int capacity;
}Stack;

void StackInit(Stack* ps);
void StackDestory(Stack* ps);
void StackPush(Stack* ps, DataType x);
DataType StackPop(Stack* ps);
bool StackEmpty(Stack* ps);
DataType StackTop(Stack* ps);

void StackInit(Stack* ps)
{
  assert(ps);

  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
void StackDestory(Stack* ps)
{
  assert(ps);

  if (ps->a != NULL) {
    free(ps->a);
    ps->a = NULL;
  }
  ps->capacity = 0;
  ps->top = 0;
}
void StackPush(Stack* ps, DataType x)
{
  assert(ps);

  if (ps->top == ps->capacity) {
    int newCapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    ps->a = (DataType*)realloc(ps->a, sizeof(DataType) * newCapcity);
    if (ps->a == NULL) {
      printf("realloc error");
      exit(-1);
    }
    ps->capacity = newCapcity;
  }

  ps->a[ps->top] = x;
  ps->top++;
}
DataType StackPop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);

  DataType data = ps->a[ps->top - 1];
  ps->a[ps->top - 1] = '\0';
  ps->top--;
  return data;
}
bool StackEmpty(Stack* ps)
{
  assert(ps);

  return ps->top == 0;
}
DataType StackTop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);

  return ps->a[ps->top - 1];
}

int priority(char ch)
{
  switch (ch) {
    case ')':
      return 0;
    case '+':
    case '-':
      return 1;
    case '*':
    case '%':
    case '/':
      return 2;
    case '^':
      return 3;
    case '(':
      return 4;
    default:
      exit(-1);
  }
}

void handleStack(char* arr, int* pos, Stack* ps, char ch)
{
  if (ch >= '0' && ch <= '9') {
    arr[(*pos)++] = ch;
    return;
  }

  if (ps->top == 0) {
    if (ch == ')') {
      exit(-1);
    }
    arr[(*pos)++] = ' ';
    StackPush(ps, ch);
    return;
  }

  if (priority(StackTop(ps)) < priority(ch)) {
    if (ch != '(') {
      arr[(*pos)++] = ' ';
    }
    StackPush(ps, ch);
    return;
  }

  while (ps->top > 0) {
    DataType data = StackTop(ps);
    if (data == '(') {
      if (ch == ')') {
        (void)StackPop(ps);
      }
      break;
    }
    if (priority(data) < priority(ch)) {
      break;
    }

    arr[(*pos)++] = ' ';
    arr[(*pos)++] = StackPop(ps);
  }

  if (ch != ')') {
    arr[(*pos)++] = ' ';
    StackPush(ps, ch);
  }
}

// 逆波兰转换运算表达式
char* transform(const char* str)
{
  assert(str);
  printf("%s\n", str);
  
  int len = strlen(str);
  if (len <= 0) {
    return NULL;
  }

  char* ttr = (char*)calloc(2 * len, sizeof(char));
  if (ttr == NULL) {
    return NULL;
  }

  Stack* ps = (Stack*)malloc(sizeof(Stack));
  if (ps == NULL) {
    return NULL;
  }
  StackInit(ps);

  int pos = 0;
  for (int i = 0; i < len; ++i) {
    if (str[i] != ' ') {
      handleStack(ttr, &pos, ps, str[i]);
    }
  }
  while (ps->top > 0) {
    ttr[pos++] = ' ';
    ttr[pos++] = StackPop(ps);
  }

  StackDestory(ps);

  return ttr;
}

int ttrToInt(const char* ttr, int len, int* arr)
{
  int anum = 0;
  for (int i = 0; i < len; ++i) {
    int start = i, val = 0;
    while (i < len && '0' <= ttr[i] && ttr[i] <= '9') {
      val = val * 10 + (ttr[i++] - '0');
    }
    if (start != i) {
      arr[anum++] = val;
    }

    if (i < len &&ttr[i] != ' ') {
      arr[anum++] = ttr[i];
    }
  }
  return anum;
}

#include<iostream>
#include<stack>

int cal(int a, int b, int op)
{
  switch (op) {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    case '/': return a / b;
    case '%': return a % b;
    default:
              exit(-1);
  }
}

int calSuffix(const int* arr, int num)
{
  std::stack<int> st;

  for (int i = 0; i < num; ++i) {
    if (0 <= arr[i] && arr[i] <= 9) {
      st.push(arr[i]);
    } else {
      int a = 0, b = 0;
      if (st.size() > 0) {
        b = st.top(); st.pop();
      } else 
        return -1;
      if (st.size() > 0) {
        a = st.top(); st.pop();
      }
      else 
        return -1;
      st.push(cal(a, b, arr[i]));
    }
  }

  return st.top();
}

int calculate(const char* ttr)
{
  if (ttr == NULL) {
    exit(-1);
  }
  printf("%s\n", ttr);

  int len = strlen(ttr);
  if (len <= 0) {
    return 0;
  }
  int* arr = (int*)malloc(len * sizeof(int));
  if (arr == NULL) {
    exit(-1);
  }
  int num = ttrToInt(ttr, len, arr);
  if (num == 0) {
    return 0;
  }

  return calSuffix(arr, num);
}

int main(int argc, char* argv[])
{
  if (argc != 2) {
    return -1;
  }

  printf("result: %d\n", calculate(transform(argv[1])));

  return 0;
}

